/* 
    深度优先遍历和广度优先遍历
    相关知识: https://www.cnblogs.com/qzhc/p/10291430.html
*/

const map = {}; // 各个顶点之间的关系; 例如: {a:[e, f], e: [c, d]}, 每个顶点保存相连接的点

/**
 * 通过两点构建连线
 * @param {*} point1
 * @param {*} point2
 */
const addSide = (point1, point2) => {
  map[point1] = map[point1] || [];
  if (map[point1].indexOf(point2) === -1) {
    map[point1].push(point2);
  }

  map[point2] = map[point2] || [];
  if (map[point2].indexOf(point1) === -1) {
    map[point2].push(point1);
  }
};

addSide("a", "b");
addSide("a", "d");
addSide("a", "f");
addSide("b", "a");
addSide("b", "g");
addSide("d", "a");
addSide("d", "c");
addSide("f", "h");
addSide("g", "e");
addSide("g", "h");
addSide("c", "d");
addSide("c", "e");

/* 
{
  a: [ 'b', 'd', 'f' ],
  b: [ 'a', 'g' ],
  d: [ 'a', 'c' ],
  f: [ 'a', 'h' ],
  g: [ 'b', 'e', 'h' ],
  c: [ 'd', 'e' ],
  h: [ 'f', 'g' ],
  e: [ 'g', 'c' ]
}
*/
// console.log(map)

/**
 * 深度优先遍历
 * @param {*} startPoint
 */
const DFS = (startPoint) => {
  const visited = []; //已经访问过的顶点

  const search = (point) => {
    visited.push(point);
    for (let val of map[point]) {
      if (visited.indexOf(val) === -1) {
        search(val);
      }
    }
  };
  search(startPoint);
  return visited;
};

// console.log(DFS("a"));

/**
 * 广度优先遍历
 * @param {*} startPoint 
 * @returns 
 */
const BFS = (startPoint) => {
  const visited = [];
  const waitVisitPoint = [startPoint]; // 等待访问的顶点, 每次访问, 将相连的顶点存放进去
  // 访问完就出队; 例如: 访问a ==> [abdf] 访问完后出队 ==>[bdf]
  //                   访问b ==> [bdfg] 访问完后出队 ==>[dfg]
  //                   访问d ==> [dfgc] 访问完后出队 ==>[fgc]

  while (waitVisitPoint.length > 0) {
    const currentPoint = waitVisitPoint.shift();
    if (visited.indexOf(currentPoint) === -1) {
      visited.push(currentPoint);

      map[currentPoint].forEach((p) => {
        waitVisitPoint.push(p);
      });
    }
  }
  return visited;
};

console.log(BFS("a"));
